package com.yj.springbootstudy.algorithm.topic;

/**
 * <h1>字符串匹配:</h1>
 * 设 S 和 T 是给定的两个串，在主串 S 中找到模式串 T 的过程称为字符串匹配，
 * 如果在主串 S 中找到 模式串 T ，则称匹配成功，函数返回 T 在 S 中首次出现的位置，否则匹配不成功，返回 -1。
 *
 * <h1>BF 算法（暴力匹配算法）：</h1>
 * 我们将模式串和主串进行比较，一致时则继续比较下一字符，直到比较完整个模式串。不一致时则将模式串后移一位，
 * 重新从模式串的首位开始对比，重复刚才的步骤下面我们看下这个方法的动图解析
 *
 *<h1>题目：</h1>
 * 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从 0 开始)。如果不存在，则返回 -1。
 */
public class Demo03 {

    public static void main(String[] args) {
        int match = match("hello", "ll");
        System.out.println(match);
    }

    /**
     * 注意：当模式串为0时，返回0，当模式串大于主串时，返回-1
     * @param haystack
     * @param needle
     * @return
     */
    public static int match(String haystack,String needle){
        int haystackLength = haystack.length();
        int needleLength = needle.length();

        if (needleLength>haystackLength){
            return -1;
        }
        if(needleLength == 0){
            return 0;
        }

        int i = 0;
        int j = 0;

        char[] arr1 = haystack.toCharArray();
        char[] arr2 = needle.toCharArray();

        while (i< arr1.length && j<arr2.length){
            if (arr1[i] == arr2[j]){
                i++;
                j++;
            }else {
                i = i-j+1;
                j = 0;
            }
            if (j == arr2.length){
                return i-j;
            }
        }
        return -1;
    }

}
